package I.堆;


import java.util.Comparator;
import java.util.PriorityQueue;

public class _剑指Offer40_最小的k个数 {
    public static void main(String[] args) {

    }
    /**
     * 使用堆来做 找前k 的最小值 所以构建小顶堆 将调整完的最顶端加入结果数组
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers(int[] arr, int k) {

        int[] result = new int[k];
        int count = 0;

        //无序数组构建
        for (int j= arr.length/2-1;j>=0;j--){
            heapsort(arr,j,arr.length);
        }

        for (int i=arr.length-1;i>0;i--){

            //交换
            int temp =arr[0];
            arr[0] = arr[i];
            //arr[i] = arr[0];


            if (count < k){
                result[count++] = temp;
            }
            heapsort(arr,0,i);

        }

        if (k== arr.length){
            result[k-1] = arr[0];
        }

       return result;
    }

    public void heapsort(int[] arr,int i,int len){
        int temp = arr[i];

        for (int k= 2*i+1;k<len;k=k*2+1){
            if (k+1 < len && arr[k]>arr[k+1]){
                k++;
            }

            if (temp > arr[k]){
                arr[i] = arr[k];
                i = k;
            }else {
                break;
            }
        }

        arr[i] = temp;
    }


    /**
     * 题解：用一个大根堆实时维护数组的前 kk 小值。首先将前 kk 个数插入大根堆中，随后从第 k+1k+1 个数开始遍历，
     * 如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可
     *
     * 使用自带的PriorityQueue--优先级队列 其底层的数据结构就是小顶堆 即升序的
     *
     */
    class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            int[] vec = new int[k];
            if (k == 0) { // 排除 0 的情况
                return vec;
            }
            PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
                //默认是小顶堆 所以重写comparator 让其降序
                public int compare(Integer num1, Integer num2) {
                    return num2 - num1;
                }
            });
            for (int i = 0; i < k; ++i) {
                queue.offer(arr[i]);
            }
            for (int i = k; i < arr.length; ++i) {
                //堆顶大了 弹出
                if (queue.peek() > arr[i]) {
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
            for (int i = 0; i < k; ++i) {
                vec[i] = queue.poll();
            }
            return vec;
        }
    }


}
